home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 3.2 / Ham Radio Version 3.2 (Chestnut CD-ROMs)(1993).ISO / packet / n17jsrc / bootpdip.c < prev    next >
C/C++ Source or Header  |  1991-05-31  |  31KB  |  1,023 lines
  1. /*
  2.  * Center for Information Technology Integration
  3.  *           The University of Michigan
  4.  *                    Ann Arbor
  5.  *
  6.  * Dedicated to the public domain.
  7.  * Send questions to info@citi.umich.edu
  8.  * BOOTP is documented in RFC 951 and RFC 1048
  9.  *
  10.  * Delinted, ANSIfied and reformatted - 5/30/91 P. Karn
  11.  */
  12.  
  13.  
  14.  
  15. /* Dynamic Ip Assignment for a Bootp Server
  16.  * Called when a client request is received and the bootp server doesnt' have a
  17.  * record for it.
  18.  *
  19.  * Design goals:
  20.  *   Assign an IP address
  21.  *   Separation/Identification of IP addresses assigned and not assigned
  22.  *   Time out mechanism to reclaim IP address
  23.  *    Timer, and arp on address with little activity
  24.  *   Reassignment to same machine if possible.
  25.  */     
  26. #include <stdio.h>
  27. #include <time.h>    
  28.  
  29. #include "global.h"
  30. #include "arp.h"
  31. #include "iface.h"
  32. #include "mbuf.h"
  33. #include "netuser.h"
  34. #include "pktdrvr.h"
  35. #include "timer.h"
  36. #include "bootpd.h"
  37.  
  38.  
  39. #define E_NOMEM 3101
  40. #define ERR_NOIPADDRESS    3103        /* No IP address available. */
  41.  
  42. #define THRESH_ON            20    /* (%) When to turn on reclaimation of IP addresses. */
  43. #define THRESH_CRITICAL       2    /* (#) */
  44. #define THRESH_OFF           50    /* (%) */
  45.  
  46. #define R_OFF                   0x01    /* Reclaimation is off. */
  47. #define R_RECLAIM               0x02    /* Reclaimation is on. */
  48. #define R_CRITICAL              0x04    /* Reclaimation is operating in critical state. */
  49. #define R_DONE                  0x08    /* Reclaimation is finishing up. */
  50. #define V_SWAIT                 0x10    /* Reclaimation is wait to start verif cycle. */
  51. #define V_VERIFY                0x20    /* Reclaimation is in verification cycle. */
  52.  
  53. #define TIME_RWAIT        (5)     /* Time between running reclm da_task */
  54. #define TIME_SWAIT              (30)    /* Time between cycles of starting address rec */
  55. #define TIME_VWAIT              (10)    /* Time to wait between sending ARPs to verify add
  56. resses. */
  57. #define TIME_ADDRRETRY          (4 * 600)       /* Time to wait before trying to reclaim a
  58. n address. */
  59. #define TIME_ADDRRECLAIM        (900)   /* Time for which an address must be in the reclai
  60. mation */
  61.                                         /* queue before being moved to the free list. */
  62.  
  63. #define RECLAIM_QUEUE_MAX       15      /* Maximum number of addresses in reclaimation queue. */
  64.  
  65.  
  66.  
  67. /*      dynamic_ip.c
  68.  *
  69.  * This file contains code to manage a range of dynamic IP addresses on a network.
  70.  */
  71.     
  72.  
  73.  
  74. /* Queue structures  */
  75.  
  76. typedef  struct  q_elt {
  77.         struct  q_elt *next;
  78. };
  79.  
  80. #define NULLQ_ELT (struct q_elt *) 0
  81.  
  82.  
  83. struct  q {
  84.         char *head;
  85.         char *tail;
  86. };
  87.  
  88. #define NULLQ_P (struct q *) 0
  89.  
  90.  
  91. /* Dynamic IP structures */
  92.  
  93. struct daddr {
  94.         struct daddr    *da_next;       /* Queue link. */
  95.         int32        da_addr;        /* IP address. */
  96.         time_t        da_time;        /* last time this address was answered for. */
  97.     char        da_hwaddr[1];   /* Hardware address, variable length. */
  98. };
  99.  
  100. #define NULLDADDR (struct daddr *) 0
  101.  
  102. struct drange_desc {
  103.         struct drange_desc *dr_next;    /* Queue link. */
  104.         struct iface    *dr_iface;      /* Pointer to network information. */
  105.     struct timer    timer;        /* Timer for reclaiming */
  106.         int32        dr_start;       /* First IP address in range. */
  107.         int32        dr_end;         /* Last IP address in range. */
  108.         int16           dr_acount;      /* Number of IP addresses in range. */
  109.         int16           dr_fcount;      /* Number of IP addresses in free. */
  110.         int16           dr_rcount;      /* Number of IP addresses on reclmation queue  */
  111.         int16           dr_thon;        /* Threshold for turning on reclaimation. */
  112.         int16           dr_thcritical;  /* Threshold for critical reclaimation. */
  113.         int16           dr_thoff;       /* Threshold for turning off reclaimation. */
  114.         int32           dr_time_addrretry;      /* Time to wait before retrying addresses.
  115.                            Varies with state. */
  116.         int16           dr_hwaddrlen;   /* Length of hardware address. */
  117.         unsigned char   dr_rstate;      /* Reclaimation state. */
  118.         unsigned char   dr_vstate;      /* Verification state. */
  119.         time_t          dr_rtime;       /* Time stamp for reclaimation. */
  120.         struct daddr    *dr_raddr;      /* Address being verified. */
  121.         struct daddr    *dr_table;      /* Pointer to table of addresses. */
  122.         struct q        dr_usedq;       /* Pointer to list of used addresses. */
  123.         struct q        dr_reclaimq;    /* Pointer to list of addrs being reclaimed.  */
  124.         struct q        dr_freeq;       /* Pointer to list of free addresses. */
  125. };
  126.  
  127. #define NULLDRANGE (struct drange_desc *) 0
  128.  
  129.  
  130.  
  131.  
  132.  
  133. #define da_structlen(dr)        (sizeof (struct daddr) + dr->dr_hwaddrlen)
  134. #define da_getnext(dr,da)       ((struct daddr *) ((unsigned char *)da + da_structlen(dr)))
  135.  
  136.  
  137. /*
  138.  * Globals.
  139.  */
  140.  
  141. int ifaceToArpMap[] = {
  142.         0,                                 /* CL_NONE */
  143.         ARP_ETHER,                             /* CL_ETHERNET */
  144.         ARP_PRONET,                             /* CL_PRONET_10 */
  145.         ARP_IEEE802,                            /* CL_IEEE8025 */
  146.         0,                                 /* CL_OMNINET */
  147.         ARP_APPLETALK,                          /* CL_APPLETALK */
  148.         0,                                   /* CL_SERIAL_LINE */
  149.         0,                                 /* CL_STARLAN */
  150.         ARP_ARCNET,                             /* CL_ARCNET */
  151.         ARP_AX25,                               /* CL_AX25 */
  152.         0,                                      /* CL_KISS */
  153.         0,                                      /* CL_IEEE8023 */
  154.         0,                                      /* CL_FDDI */
  155.         0,                                      /* CL_INTERNET_X25 */
  156.         0,                                      /* CL_LANSTAR */
  157.         0,                                      /* CL_SLFP */
  158.         ARP_NETROM,                             /* CL_NETROM */
  159.         0                                       /* NCLASS */
  160. };
  161.  
  162.  
  163.  
  164. static struct q                 rtabq;
  165. struct timer            da_timer;
  166. char                bp_ascii[128];
  167.  
  168. static void da_runtask __ARGS((void *arg));
  169. struct q_elt *q_dequeue __ARGS((struct q *queue));
  170. static void da_closeup __ARGS((struct drange_desc *dr));
  171. static void dprint_addresses __ARGS((struct drange_desc *dr));
  172. static int q_remove __ARGS((struct q *source_queue,struct q_elt *qel));
  173. static void iptoa __ARGS((int32 ipaddr,char ipstr[16]));
  174. static void da_task __ARGS((void));
  175. static int da_fill_reclaim __ARGS((struct drange_desc *dr));
  176. static void da_do_verify __ARGS((struct drange_desc *dr,int pendtime));
  177. static void da_enter_reclaim __ARGS((struct drange_desc *dr));
  178. static void da_enter_done __ARGS((struct drange_desc *dr));
  179. static void da_enter_off __ARGS((struct drange_desc *dr));
  180. static void q_enqueue __ARGS((struct q     *queue,struct q_elt *elem));
  181. static int da_get_old_addr __ARGS((struct drange_desc *dr,char *hwaddr,struct daddr **dap));
  182. static int da_get_free_addr __ARGS((struct drange_desc *dr,struct daddr **dap));
  183. static void da_enter_critical __ARGS((struct drange_desc *dr));
  184. static void q_init __ARGS((struct q *queue));
  185.  
  186. extern int bp_ReadingCMDFile;
  187.  
  188.  
  189.  
  190. /*
  191.  * Shutdown routines.
  192.  */
  193.  
  194. /*
  195.  * Done serving a network.
  196.  */
  197. da_done_net(iface)
  198. struct iface *iface;
  199. {
  200.         struct drange_desc *dr;
  201.  
  202.         /* Find the network table */
  203.         for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  204.                 if(iface == dr->dr_iface)
  205.                         break;
  206.         }
  207.  
  208.         if(dr == NULLDRANGE){
  209.         bp_log("Range for interface '%s' not found.\n", iface->name);
  210.         return -1;
  211.     }
  212.  
  213.         da_closeup(dr);
  214.     bp_log("Range removed for iface %s\n", iface->name);
  215.         return 0;
  216. }
  217.  
  218.  
  219.  
  220.  
  221. /*
  222.  * Print the status of the da structures.
  223.  */
  224. void
  225. da_status(iface)
  226. struct iface *iface;
  227. {
  228.         struct drange_desc *dr;
  229.  
  230.     /* If no interface was specified, print all the range information */
  231.     if(iface == NULLIF){
  232.             for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; 
  233.          dr = dr->dr_next) 
  234.             dprint_addresses(dr);
  235.     
  236.     } else {
  237.         /* Print the specified range's information */
  238.         /* Find the specified interface */
  239.             for(dr = (struct drange_desc *) rtabq.head; 
  240.          (dr != NULLDRANGE) && (dr->dr_iface != iface); 
  241.          dr = dr->dr_next)
  242.             ; 
  243.         
  244.         /* If network not found, return */
  245.         if(dr == NULLDRANGE){
  246.             tprintf("Range for interface '%s' not found.\n", iface->name);
  247.             return;    
  248.         }
  249.         /* The range has been found.  Print it. */
  250.         dprint_addresses(dr);
  251.     }
  252. }
  253.  
  254.  
  255.  
  256. /*
  257.  * Finish up service.  Close up on each of the address ranges.
  258.  */
  259. void
  260. da_shut()
  261. {
  262.         struct drange_desc *dr;
  263.  
  264.     stop_timer(&da_timer);
  265.         while((dr = (struct drange_desc *)q_dequeue (&rtabq)) != NULLDRANGE)
  266.                 da_closeup(dr);
  267. }
  268.  
  269.  
  270. /*
  271.  * Release resource for a network.
  272.  */
  273. static void
  274. da_closeup(dr)
  275. struct drange_desc *dr;
  276. {
  277.         free(dr->dr_table);            /* Free the address table. */
  278.         q_remove(&rtabq, (struct q_elt *)dr);    /* Dequeue the range descriptor. */
  279.         free(dr);                /* Free the range descriptor. */
  280. }
  281.  
  282.  
  283.  
  284. /* This is only called from a command */
  285. static void
  286. dprint_addresses(dr)
  287. struct drange_desc *dr;
  288. {
  289.         struct daddr *da;
  290.         char ipa[16];
  291.     char ipb[16];
  292.     struct arp_type    *at;
  293.     
  294.     at = &Arp_type[dr->dr_iface->type];
  295.  
  296.     iptoa(dr->dr_start, ipa);
  297.     iptoa(dr->dr_end, ipb);
  298.     tprintf("Interface %s range: %s - %s\n", dr->dr_iface->name, ipa, ipb);
  299.  
  300.         da = (struct daddr *) dr->dr_freeq.head;
  301.     tprintf("Free address queue\n");
  302.         while(da){
  303.                 iptoa(da->da_addr, ipa);
  304.                 tprintf("    %s  last used by %s\n", ipa,(*at->format)(bp_ascii, da->da_hwaddr));
  305.                 da = da->da_next;
  306.         }
  307.  
  308.         da = (struct daddr *) dr->dr_usedq.head;
  309.         tprintf("\nUsed address queue\n");
  310.         while(da){
  311.                 iptoa(da->da_addr, ipa);
  312.                 tprintf("    %s  in use by %s\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
  313.                 da = da->da_next;
  314.         }
  315.  
  316.         da =(struct daddr *) dr->dr_reclaimq.head;
  317.         tprintf("\nReclaimation address queue\n");
  318.         while(da){
  319.                 iptoa(da->da_addr, ipa);
  320.                 tprintf("    %s  in use by %s?\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
  321.                 da = da->da_next;
  322.         }
  323.         tprintf("\n");
  324. }
  325.  
  326.  
  327.  
  328. /*
  329.  * Reclaimation routines.
  330.  */
  331. static void
  332. da_runtask(p)
  333. void *p;
  334. {
  335.     stop_timer(&da_timer);
  336.     da_task();
  337.     set_timer(&da_timer,TIME_RWAIT*1000L);
  338.     start_timer(&da_timer);
  339. }
  340.  
  341. /*
  342.  * Called periodically to run reclaimation.
  343.  */
  344. static void
  345. da_task()
  346. {
  347.     struct drange_desc *dr;
  348.     time_t now;
  349.     int arpHardware, arpPendtime;
  350.  
  351.     now = time(NULL);
  352.  
  353.     for(dr = (struct drange_desc *)rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  354.  
  355.         arpHardware = ifaceToArpMap [dr->dr_iface->type];
  356.         arpPendtime = Arp_type[arpHardware].pendtime;
  357.  
  358.         if(!(dr->dr_rstate & R_OFF)){    /* If doing reclaimation on this range. */
  359.             if(dr->dr_vstate == V_SWAIT){    /* If in wait sub-state. */
  360.                 /* Doing reclaimation on this range and am waiting to 
  361.                  * start a cycle of address
  362.                  * verification.  Check if it is time to start the 
  363.                  * cycle. */
  364.  
  365.                 if(now - dr->dr_rtime > TIME_SWAIT){
  366.                     /* Start the cycle.  */
  367.                     if(!(dr->dr_rstate & R_DONE))
  368.                         da_fill_reclaim(dr);
  369.  
  370.                     dr->dr_vstate = V_VERIFY; /* verify sub-state. */
  371.                     dr->dr_raddr = NULLDADDR; /* start at beginning */
  372.                 }
  373.             }
  374.             /* If in the verify state (may have just been changed above), and 
  375.              * enough time has passed since last lookup, check it and start
  376.              * the next lookup. */
  377.  
  378.             if(dr->dr_vstate == V_VERIFY){
  379.                 if(now - dr->dr_rtime > arpPendtime){
  380.                     da_do_verify(dr, arpPendtime); /* Verify address. */
  381.                     dr->dr_rtime = time(NULL); /* Set time stamp. */
  382.                     if(dr->dr_raddr == NULLDADDR){ /* If at end... */
  383.                         dr->dr_vstate = V_SWAIT; /* Q empty; enter wait sub-state. */
  384.                     }
  385.                 }
  386.             }
  387.             
  388.             /* 
  389.              * State transitions.  May have moved some addresses to free list.
  390.              * If so, I may be able to move to a "lower" state.
  391.              */
  392.             switch(dr->dr_rstate){
  393.             /* case R_OFF: Not handled. */
  394.             case R_CRITICAL:
  395.                 /* Have conditions droped below critical threshhold? */
  396.                 if(dr->dr_fcount > dr->dr_thcritical)    
  397.                     da_enter_reclaim(dr);
  398.                 /* Fall through. */
  399.             case R_RECLAIM:
  400.                 /* Have I reclaimed enough addresses? */
  401.                 if(dr->dr_fcount > dr->dr_thoff)    
  402.                     da_enter_done(dr);
  403.                 /* Fall through. */
  404.             case R_DONE:
  405.                 /* Am I in the done state and have exausted the reclaimation queue? */
  406.                 if((dr->dr_rstate & R_DONE) && dr->dr_reclaimq.head == NULLCHAR) 
  407.                     da_enter_off(dr);
  408.                 break;
  409.             }
  410.         }
  411.     }
  412. }
  413.  
  414.  
  415.  
  416.  
  417. /* 
  418.  * Enter the DONE state.  Can't get to the done state from the off state.
  419.  */
  420. static void
  421. da_enter_done(dr)
  422. struct drange_desc *dr;
  423. {
  424.     char ipa[16], ipb[16];
  425.     
  426.     iptoa(dr->dr_start, ipa);
  427.     iptoa(dr->dr_end, ipb);
  428.  
  429.     if((dr->dr_rstate & R_OFF) == 0){ 
  430.         dr->dr_rstate = R_DONE;
  431.         dr->dr_time_addrretry = TIME_ADDRRETRY;        /* Wait a while before retrying addresses. */
  432.     }
  433. }
  434.  
  435.  
  436. /* 
  437.  * Enter the OFF state.
  438.  */
  439. static void
  440. da_enter_off(dr)
  441. struct drange_desc *dr;
  442. {
  443.     char ipa[16], ipb[16];
  444.     
  445.     iptoa(dr->dr_start, ipa);
  446.     iptoa(dr->dr_end, ipb);
  447.  
  448.     dr->dr_rstate = R_OFF;
  449. }
  450.  
  451.  
  452. /*
  453.  * Verify addresses.
  454.  * To avoid flodding the network and our address resolution queue I only send
  455.  * out one ARP at a time.  This routine is called periodically to step through
  456.  * the reclaimation queue.  The first step is to check for a responce to the
  457.  * ARP that was sent out previously.  If there is a responce I move the address
  458.  * to the used queue. The next step is to send out an ARP for the next address
  459.  * on the recliamation queue. After a suitable intervel (TIME_VTIME) I'll be
  460.  * called again.
  461.  */
  462. static void
  463. da_do_verify(dr, pendtime)
  464. struct drange_desc *dr;
  465. int pendtime;
  466. {
  467.     struct daddr *da, *dn;
  468.     struct iface *iface;
  469.     long now;
  470.     struct arp_tab *ap;
  471.     int16 arpType;
  472.     
  473.      now = time(NULL);
  474.      iface = dr->dr_iface;
  475.     arpType = ifaceToArpMap[iface->type];
  476.  
  477.     /*
  478.       * If I sent an ARP for an address, check if that ARP has been responded to.
  479.      * If dr_raddr points to an address record, I have previously sent an
  480.      * ARP for that address.  Check the ARP cache for a responce.
  481.      * If dr_raddr is NULL then I am to start at the head of the reclaim queue.
  482.       */
  483.  
  484.     if(dr->dr_raddr != NULLDADDR){
  485.         /* ARP has been sent for dr_raddr.  Check the ARP cache for a responce. */
  486.         da = dr->dr_raddr;
  487.         dn = da->da_next;
  488.  
  489.         ap = arp_lookup(arpType, da->da_addr);
  490.  
  491.         if((ap != NULLARP) && (ap->state == ARP_VALID)){
  492.             /* Host responded to arp.  Place address on used queue.
  493.              * Copy in physical address of host using address to
  494.              * make sure our info is up to date.  
  495.              * I could verify that physical address of host
  496.              * responding to  ARP matches the physical address of
  497.              * the host I think owns the address.  If don't match
  498.              * someone is probably using an incorrect address.
  499.              */
  500.  
  501.             q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
  502.             --dr->dr_rcount;
  503.             da->da_time = now;        /* Time tested. */
  504.             memcpy(da->da_hwaddr, ap->hw_addr, Arp_type[ap->hardware].hwalen);
  505.             q_enqueue(&dr->dr_usedq, (struct q_elt *)da);
  506.  
  507.         } else {
  508.             /* Host did not respond to ARP.  If addr on reclaim
  509.              * queue long enough, move it to the free queue.
  510.              */
  511.             if(now - da->da_time >= pendtime){
  512.                 q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
  513.                 --dr->dr_rcount;
  514.                 q_enqueue(&dr->dr_freeq,(struct q_elt *)da);
  515.                 ++dr->dr_fcount;
  516.                 bp_log("Reclaimed address %s on net %s.\n", 
  517.                     inet_ntoa(da->da_addr), dr->dr_iface->name);
  518.             }
  519.         }
  520.     } else {
  521.         /* Use first addr in reclaimq. */
  522.         dn = (struct daddr *) dr->dr_reclaimq.head;
  523.     }
  524.     /*
  525.       * Now move to the next entry in the queue and ARP for it.
  526.       */
  527.      da = dn;
  528.     if(da != NULLDADDR){
  529.         ap = arp_lookup(arpType, da->da_addr);
  530.         if(ap != NULLARP) arp_drop(ap);
  531.         res_arp(iface, arpType, da->da_addr, NULLBUF);
  532.     }
  533.     dr->dr_raddr = da;    /* Verify this address next time around. */
  534.     dr->dr_rtime = time(NULL);
  535. }
  536.  
  537.  
  538. /*
  539.  * Fill the reclaimation list from the used list.  Take addresses off the head
  540.  * of the used queue until the reclaim queue is full, the used queue is empty,
  541.  * or the address at the head of the used queue has been verified (responded
  542.  * to an ARP) within dr_time_addrretry tocks.
  543.  */
  544. static int
  545. da_fill_reclaim(dr)
  546. struct drange_desc *dr;
  547. {
  548.         struct daddr *da;
  549.         long now;
  550.  
  551.         now = time(NULL);
  552.  
  553.         while(dr->dr_rcount < RECLAIM_QUEUE_MAX){
  554.         /* Look at first address on used queue. */
  555.                 da = (struct daddr *) dr->dr_usedq.head;
  556.                 if(da == NULLDADDR)
  557.             return 0;    /* If used queue is empty, done filling. */
  558.                 if(now - da->da_time < dr->dr_time_addrretry)
  559.                         return 0;
  560.  
  561.         /* If the first element has responded to in ARP recently.
  562.          * I am done filling.
  563.          */
  564.         /* Get first address on used queue. */
  565.                 da = (struct daddr *) q_dequeue(&dr->dr_usedq);
  566.         /* Mark time addr put in reclaim queue. */
  567.                 da->da_time = now;
  568.         /* Put it at end of reclaim queue. */
  569.                 q_enqueue(&dr->dr_reclaimq,(struct q_elt *)da);
  570.                 ++dr->dr_rcount;
  571.         }
  572.         return 0;
  573. }
  574.  
  575.  
  576. /*
  577.  * Address assignment routines.
  578.  */
  579.  
  580. /*
  581.  * Assign an address.
  582.  */
  583. int
  584. da_assign(iface, hwaddr, ipaddr)
  585. struct iface *iface;    /* -> Pointer to lnet struct of net on which to assign addr. */
  586. char    *hwaddr;    /* -> Pointer to hardware address of hosts. */
  587. int32    *ipaddr;    /* <- Address assigned to host. */
  588. {
  589.     struct drange_desc *dr;    
  590.     struct daddr *da;    
  591.     int status;
  592.     struct arp_type    *at;
  593.  
  594.     /* Find the network table */
  595.     for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  596.         if(iface == dr->dr_iface)
  597.             break;    
  598.     }
  599.  
  600.     if(dr == NULLDRANGE){
  601.         *ipaddr = 0;
  602.         return ERR_NOIPADDRESS;
  603.     }
  604.  
  605.     /* If this host had an address assigned previously, try to reassign
  606.      * that. If no previous address, assign a new one.
  607.      */
  608.     status = da_get_old_addr(dr, hwaddr, &da);
  609.     if(status != 0) 
  610.         status = da_get_free_addr(dr, &da);
  611.     
  612.     /* If I got an address, assign it and link it in to the use list. */
  613.     if(status == 0){
  614.         memcpy(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen);
  615.         *ipaddr = da->da_addr;
  616.         da->da_time = time(NULL);    /* Time assigned */
  617.         q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
  618.         at = &Arp_type[dr->dr_iface->type];
  619.         bp_log("IP addr %s assigned to %s on network %s\n",
  620.          inet_ntoa(*ipaddr),
  621.          (*at->format)(bp_ascii, hwaddr), dr->dr_iface->name);
  622.     }
  623.  
  624.         switch(dr->dr_rstate){
  625.         case R_OFF:
  626.         case R_DONE:
  627.                 if(dr->dr_fcount <= dr->dr_thon) 
  628.             da_enter_reclaim(dr);
  629.                 /* Fall through. */
  630.         case R_RECLAIM:
  631.                 if(dr->dr_fcount <= dr->dr_thcritical) 
  632.             da_enter_critical(dr);
  633.                 break;
  634.         /* case R_CRITICAL: is not handled. */
  635.         }
  636.         return status;
  637. }
  638.  
  639.  
  640. /*
  641.  * Enter the reclaimation state.
  642.  */
  643. static void
  644. da_enter_reclaim(dr)
  645. struct drange_desc *dr;
  646. {
  647.         char ipa[16], ipb[16];
  648.  
  649.         iptoa(dr->dr_start, ipa);
  650.         iptoa(dr->dr_end, ipb);
  651.  
  652.         if(dr->dr_rstate & R_OFF){
  653.                 dr->dr_vstate = V_SWAIT;  /* da_enter_reclaim: R_OFF */
  654.                 dr->dr_rtime = 0;
  655.         }
  656.         dr->dr_rstate = R_RECLAIM;
  657.         dr->dr_time_addrretry = TIME_ADDRRETRY;         /* Wait a while before retrying addresses. */
  658. }
  659.  
  660. /*
  661.  * Search for hwaddr on the used list, the reclaimation list, and the free list.
  662.  */
  663. static int
  664. da_get_free_addr(dr, dap)
  665. struct drange_desc *dr;
  666. struct daddr **dap;
  667. {
  668.         *dap = (struct daddr *) q_dequeue(&(dr->dr_freeq));
  669.         if(*dap == NULLDADDR) 
  670.         return ERR_NOIPADDRESS;
  671.         --dr->dr_fcount;
  672.  
  673.         return 0;
  674. }
  675.  
  676. /*
  677.  * Search for hwaddr on the used list, the reclaimation list, and the free list.
  678.  */
  679. static int
  680. da_get_old_addr(dr, hwaddr, dap)
  681. struct drange_desc *dr;
  682. char       *hwaddr;
  683. struct daddr **dap;
  684. {
  685.         struct daddr *da;
  686.  
  687.     /* Search the used queue */
  688.         for(da = (struct daddr *) dr->dr_usedq.head; da != NULLDADDR; da = da->da_next){
  689.                 if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
  690.                         q_remove(&dr->dr_usedq,(struct q_elt *)da);
  691.                         *dap = da;
  692.                         return 0;
  693.                 }
  694.         }
  695.  
  696.     /* Search the relaimq queue */
  697.         for(da = (struct daddr *) dr->dr_reclaimq.head; da != NULLDADDR; 
  698.         da = da->da_next){
  699.                 if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
  700.                         /* Here is the address.  I have to be carefull in removing it from
  701.              * reclaim queue, I may be verifying this address.
  702.                          * If I am, I have to fix up the pointers before removing this
  703.                          * element.
  704.                          */
  705.                         if((dr->dr_rstate & R_OFF) == 0 && dr->dr_vstate == V_VERIFY 
  706.                 && dr->dr_raddr == da){ 
  707.                 /* I am verifying this very address.  */
  708.                                 /* Start over.  
  709.                  * This should happen very infrequently at most. */
  710.                                 dr->dr_vstate = V_SWAIT;  /* get_old_addr */
  711.                         }
  712.                         q_remove(&dr->dr_reclaimq,(struct q_elt *)da);
  713.                         *dap = da;
  714.                         return 0;
  715.                 }
  716.         }
  717.  
  718.     /* Search the free queue */
  719.         for(da = (struct daddr *) dr->dr_freeq.head; da != NULLDADDR; da = da->da_next){
  720.                 if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
  721.                         q_remove(&dr->dr_freeq,(struct q_elt *)da);
  722.                         --dr->dr_fcount;
  723.                         *dap = da;
  724.                         return 0;
  725.                 }
  726.         }
  727.         return ERR_NOIPADDRESS;
  728. }
  729.  
  730. #ifdef    notdef
  731. static void
  732. dprint_dr_record(dr)
  733. struct drange_desc *dr;
  734. {
  735.         bp_log("Queue link   x%lx\n", dr->dr_next);
  736.         bp_log("Pointer to network information         x%lx\n", dr->dr_iface);
  737.         bp_log("First IP address in range              x%lx\n", dr->dr_start);
  738.         bp_log("Last IP address in range               x%lx\n", dr->dr_end);
  739.         bp_log("Number of IP addresses in range        %d\n", dr->dr_acount);
  740.         bp_log("Number of IP addresses in free         %d\n", dr->dr_fcount);
  741.         bp_log("Number of IP addresses on reclaimation queue %d\n", 
  742.         dr->dr_rcount);
  743.         bp_log("Threshold for turning on reclaimation  %d\n", dr->dr_thon);
  744.         bp_log("Threshold for critical reclaimation    %d\n", dr->dr_thcritical);
  745.         bp_log("Threshold for turning off reclaimation %d\n", dr->dr_thoff);
  746.         bp_log("Time to wait before retrying addresses %ld\n", 
  747.         dr->dr_time_addrretry);
  748.         bp_log("Length of hardware address             %d\n", dr->dr_hwaddrlen);
  749.         bp_log("Reclaimation state                     %d\n",(int)dr->dr_rstate);
  750.         bp_log("Verification state                     %d\n",(int)dr->dr_vstate);
  751.         bp_log("Time stamp for reclaimation            %ld\n", dr->dr_rtime);
  752.         bp_log("Address being verified                 x%lx\n", dr->dr_raddr);
  753.         bp_log("Pointer to table of addresses          x%lx\n", dr->dr_table);
  754.         bp_log("uesdq x%lx  reclaimq                   x%lx  freeq x%lx\n", dr->dr_usedq, 
  755.         dr->dr_reclaimq, dr->dr_freeq);
  756. }
  757. #endif
  758.  
  759.  
  760. /*
  761.  * Enter the critical reclaimation state.
  762.  */
  763. static void
  764. da_enter_critical(dr)
  765. struct drange_desc *dr;
  766. {
  767.         char ipa[16], ipb[16];
  768.     char *ipc;
  769.  
  770.     ipc = inet_ntoa(dr->dr_start);
  771.     strcpy(ipa, ipc);
  772.     ipc = inet_ntoa(dr->dr_end);
  773.     strcpy(ipb, ipc);
  774.  
  775.         if((dr->dr_rstate & R_OFF) == 0){
  776.                 dr->dr_vstate = V_SWAIT;    /* Enter critical, & R_OFF */
  777.                 dr->dr_rtime = 0;
  778.         }
  779.         dr->dr_rstate = R_CRITICAL;
  780.         dr->dr_time_addrretry = 0;      /* Retry addresses as fast as possible. */
  781. }
  782.  
  783. /*
  784.  * Initialization    
  785.  */
  786. /*
  787.  * Initialize the Dynamic address assignment module.
  788.  */
  789. int
  790. da_init()
  791. {
  792.         q_init(&rtabq);
  793.         return 0;
  794. }
  795.  
  796. /*
  797.  * Begin dynamic address service for a network.
  798.  */
  799. int
  800. da_serve_net(iface, rstart, rend)
  801. struct iface *iface;        /* Pointer to lnet record. */
  802. int32 rstart;            /* First address in range. */
  803. int32 rend;            /* Last address in range. */
  804. {
  805.     struct drange_desc *dr;    /* Pointer to the range descriptor. */
  806.     struct daddr *da;    /* Pointer to an address structure. */
  807.     int32 rcount;        /* Number of addresses range. */
  808.     time_t now;        /* Current time. */
  809.     int16 i;
  810.     char ipc[16], ipd[16];
  811.  
  812.         /* Find the network table */
  813.         for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE;
  814.      dr = dr->dr_next){
  815.                 if(iface == dr->dr_iface)
  816.                         break;
  817.         }
  818.  
  819.     
  820.     if(dr == NULLDRANGE){
  821.         /* If there is no network table, allocate a new one
  822.          *
  823.           * Allocate the memory I need.
  824.           */
  825.         dr = (struct drange_desc *) calloc(1, sizeof(*dr));
  826.         if(dr == NULLDRANGE) 
  827.             return E_NOMEM;
  828.     } else if((dr->dr_start != rstart) || (dr->dr_end != rend)) 
  829.         /* If the range is different, create a new range */
  830.         free(dr->dr_table);
  831.     else
  832.         return 0; /* There is no change, return */
  833.  
  834.  
  835.     rcount = (rend - rstart) + 1;
  836.     da = (struct daddr *) calloc(1,(sizeof (*da) + iface->iftype->hwalen) * rcount);
  837.     if(da == NULLDADDR) 
  838.         return E_NOMEM;
  839.  
  840.     /* 
  841.      * Got the memory, fill in the structures.
  842.      */
  843.     dr->dr_iface = iface;
  844.     dr->dr_start = rstart;
  845.     dr->dr_end = rend;
  846.     dr->dr_acount = rcount;
  847.     dr->dr_fcount = 0;
  848.     dr->dr_rcount = 0;
  849.     dr->dr_thon = (rcount * THRESH_ON) / 100;
  850.     dr->dr_thcritical = THRESH_CRITICAL;
  851.     dr->dr_thoff = (rcount * THRESH_OFF) / 100;
  852.     dr->dr_time_addrretry = 0;
  853.         dr->dr_hwaddrlen = iface->iftype->hwalen;
  854.     dr->dr_rstate = R_OFF;
  855.     dr->dr_vstate = V_SWAIT;            /* Initialize */
  856.     dr->dr_rtime = 0;
  857.     dr->dr_raddr = NULLDADDR;
  858.     dr->dr_table = da;
  859.  
  860.     /* 
  861.      * Fill in the table and link them all onto the used list.
  862.      */
  863.     time(&now);
  864.     for(i = 0, da = dr->dr_table; i < dr->dr_acount; ++i, da = da_getnext(dr, da)){
  865.         da->da_addr = rstart++;
  866.         da->da_time = 0;        /* Initiallize at 0, only here */
  867.         q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
  868.     }
  869.     /* and set up the timer stuff */
  870.     if(rtabq.head == NULLCHAR){
  871.         set_timer(&da_timer,TIME_RWAIT*1000L);
  872.                da_timer.func = da_runtask;
  873.                da_timer.arg = (void *) 0;
  874.         start_timer(&da_timer);
  875.     }
  876.     q_enqueue(&rtabq,(struct q_elt *)dr);
  877.     da_enter_critical(dr);    /* Start reclaiming some of these addresses. */
  878.  
  879.     iptoa(dr->dr_start, ipc);
  880.     iptoa(dr->dr_end, ipd);
  881.     bp_log("DynamicIP range: %s - %s\n", ipc, ipd);
  882.     return 0;
  883. }
  884.  
  885.  
  886. /*
  887.  * Routines to implement a simple forward linked queue.
  888.  */
  889.  
  890. /*
  891.  *      q_init()
  892.  *      Initialize simple Q descriptor
  893.  */
  894. static void
  895. q_init(queue)
  896. struct q *queue;
  897. {
  898.         queue->head = 0;
  899.         queue->tail = 0;
  900. }
  901.  
  902.  
  903. /*
  904.  *      q_enqueue()
  905.  *              Enqueue an element in a simple Q.
  906.  */
  907. void
  908. q_enqueue(queue, elem)
  909. struct q *queue;
  910. struct q_elt *elem;
  911. {
  912.         struct q_elt *last;
  913.  
  914.         if(queue->tail != NULLCHAR){  /* If not empty Q... */
  915.                 last = (struct q_elt *) queue->tail;
  916.                 last->next = elem;
  917.         }
  918.         else
  919.         queue->head = (char *) elem;
  920.  
  921.         queue->tail = (char *) elem;
  922.         elem->next = NULLQ_ELT;
  923. }
  924.  
  925.  
  926. /*
  927.  *      q_dequeue       ()
  928.  *      Pull an element off of the head of a Q.
  929.  */
  930. struct q_elt *
  931. q_dequeue(queue)
  932. struct q *queue;
  933. {
  934.         struct q_elt *elem;
  935.  
  936.         if(queue->head == NULLCHAR)
  937.         return NULLQ_ELT; /* return NULL when empty Q */
  938.         elem = (struct q_elt *) queue->head;
  939.         queue->head = (char *) elem->next;
  940.         elem->next = NULLQ_ELT;
  941.         if(queue->head == NULLCHAR)
  942.         queue->tail = NULLCHAR;
  943.         return elem;
  944. }
  945.  
  946.  
  947. /*
  948.  *      Remove an element from the middle of a queue.  Note that
  949.  *      there is no mutex here, so this shouldn't be used on
  950.  *      critical Qs
  951.  */
  952.  
  953. static int
  954. q_remove(source_queue, qel)
  955. struct q *source_queue;
  956. struct q_elt *qel;
  957. {
  958.         struct q_elt *prev, *e;
  959.  
  960.         /*   Case : removing first in Q */
  961.  
  962.         if(qel == (struct q_elt *) source_queue->head){
  963.                 source_queue->head = (char *)qel->next;  /* trying to remove first in queue... */
  964.                 if(source_queue->head == NULLCHAR)      /* nothing left... */
  965.                         source_queue->tail = NULLCHAR;     /* blank out the Q */
  966.                 else if(source_queue->head == source_queue->tail){ /* One thing left */
  967.                         e = (struct q_elt *) source_queue->head; /* As insurance, set it's next to NULL. */
  968.                         e->next = NULLQ_ELT;
  969.                 }
  970.                 return 0;
  971.         }
  972.  
  973.         /* find Q element before qel, so that we can link around qel */
  974.         for(prev = (struct q_elt *) source_queue->head; prev->next != qel; prev = prev->next)
  975.                 if(prev == NULLQ_ELT)
  976.                         return 1;
  977.  
  978.         /* Case : Removing last in Q */
  979.  
  980.         if(qel == (struct q_elt *) source_queue->tail){     /* trying to remove last one in queue... */
  981.                 prev->next = NULLQ_ELT;   /* there is a prev elt, since we return on first */
  982.                 source_queue->tail = (char *) prev;
  983.                 return 0;
  984.         }
  985.  
  986.         /*  else, removing a queue element in the middle...  */
  987.         prev->next = qel->next;
  988.         return 0;
  989. }
  990.  
  991. /*
  992.  * Support Routines
  993.  */
  994.  
  995. static void
  996. iptoa(ipaddr, ipstr)
  997. int32 ipaddr;
  998. char ipstr[16];
  999. {
  1000.     char *tmpStr;
  1001.  
  1002.     tmpStr = inet_ntoa(ipaddr);
  1003.     strcpy(ipstr, tmpStr);
  1004. }
  1005.  
  1006.  
  1007. #ifdef    notdef
  1008. static  void
  1009. build_hex_string(fromstr, len, tostr)
  1010. char *fromstr; int  len;
  1011. char *tostr;
  1012. {
  1013.     int i;
  1014.  
  1015.     for(i=0; i < len; i++){
  1016.         sprintf(tostr, "%02x", fromstr[i]);
  1017.         tostr++;
  1018.         tostr++;
  1019.     }
  1020.     fromstr[len] = 0;
  1021. }
  1022. #endif
  1023.